package io.yunho.yunho.interview.one.program;

import java.util.Random;

/**
 * @author: Jason
 * @date: 2021/3/9 16:42
 * @description:
 */
public class NStepTest {
    public static void main(String[] args) {
        //胡思乱想
//        int methodnum = howrun(n,0,0);
//        Random r  = new Random(2);
//        int i = r.nextInt(2);
////        while (i!=1 && i!= 2){
////            i = r.nextInt();
////        }
//        System.out.println(i);
        //正确思路 递归 代码比较简单 有助于阅读 但是效率较低
        //f(n) = f(n-2)+f(n-1) n个台阶的走法等于n-2个台阶的走法+n-1个台阶的走法
        int n = 25;
        long dstart = System.currentTimeMillis();
        System.out.println(f(n));
        long dend = System.currentTimeMillis();
        System.out.println(dend-dstart);//毫秒
//        //效率更高的思路 循环迭代
//        dstart = System.currentTimeMillis();
//        System.out.println(loop(n));
//        dend = System.currentTimeMillis();
//        System.out.println(dend-dstart);//毫秒
    }

    private static int loop(int n) {
        if(n<1){
            throw new IllegalArgumentException("参数不能小于1");
        }
        if(n==1 || n==2){
            return n;
        }
        //最后需要走两步的台阶为n-2 那么到n-2的可能性就是f(n-2) 这个可能性的数量为two
        //同理，最后需要走一步的台阶为n-1  n-1之前可能性为f(n-1) 这个可能性的数量为one，注意：two再走一步就是one，也就是说one就是two走走完一步后的可能性数量
        int two = 1;//假设为3的话 那么two就是走了1步，还差2步
        int one = 2;//假设为3的话 那么one就是已经走了两步了，差1步
        int sum=0;
        for(int i=3;i<=n;i++){
            sum = two+one;
            two = one;
            one = sum;
        }
        return sum;
    }

    private static int f(int n){
        if(n<1){
            throw new IllegalArgumentException("参数不能小于1");
        }
        if(n==1 || n==2){
            return n;
        }
        int kk =f(n-1)+f(n-2);
        if(kk > Integer.MAX_VALUE){
            throw new IllegalArgumentException("参数过大，导致返回超出存储边界");
        }
        return f(n-1)+f(n-2);
    }

//    private static int howrun(int num, int start,int now) {
//        if(now == num-1){
//            return 1;
//        }
//        if(now == num-2){
//            return 2;
//        }
//        if(start == 2){
//            now = howrun(num,1,now);
//        }else{
//            now +=2;
//            now = now + howrun(num,2,now);
//        }
//    }
}
